// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-27 10:53
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

public class Jump {
    public int jump(int[] nums) {
        // 寻找区域范围内的最大值和数组长度进行比较
        // len - nums[k] is min
        int step = 0;
        int len = nums.length;
        int start = nums[0];
        if (start == 0) return 0;
        if (start == 1 && len == 1) return 0;
        int i = 0;
        int tI = 0;
        int tStart = 0;
        while (true) {
            for (int j = 0; j <= start; j++) {
                // 起点区域内的最大值
                if (len <= start + nums[j]) {
                    return step + 1;
                }
                if ((len - tStart) >= (len - nums[i + j])) {
                    // 新来的够格
                    tStart = nums[i + j];
                    tI = i + j;
                }
            }
            start = tStart;
            i = tI;
            ++step;

        }

    }
}
